package com.klun.project.common.constans.leetcode;
//给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
// 有效 二叉搜索树定义如下：
// 节点的左子树只包含 小于 当前节点的数。
// 节点的右子树只包含 大于 当前节点的数。
// 所有左子树和右子树自身必须也是二叉搜索树。
//
// 示例 1：
//输入：root = [2,1,3]
//输出：true
//
// 示例 2：
//输入：root = [5,1,4,null,null,3,6]
//输出：false
//解释：根节点的值是 5 ，但是右子节点的值是 4 。
//
// 提示：
// 树中节点数目范围在[1, 104] 内
// -231 <= Node.val <= 231 - 1
// Related Topics 树 深度优先搜索 二叉搜索树 二叉树

import com.klun.project.common.constans.entity.TreeNode;
import com.klun.project.common.constans.utils.ParseUtils;

public class Solution98 {
	public boolean isValidBST(TreeNode root) {
		if (null == root) return true;
		return dfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
	}

	public boolean dfs(TreeNode node, Long min, Long max) {
		if (null == node) return true;
		if (node.val <= min || node.val >= max) return false;
		return dfs(node.left, min, (long) node.val) && dfs(node.right, (long) node.val, max);
	}

	public static void main(String[] args) {
		Solution98 solution = new Solution98();
		TreeNode treeNode = ParseUtils.ArrayToBTree("[5,1,4,null,null,3,6]");
		TreeNode treeNode1 = ParseUtils.ArrayToBTree("[5,4,6,null,null,3,7]");
		TreeNode treeNode2 = ParseUtils.ArrayToBTree("[2147483647]");
		System.out.println(solution.isValidBST(treeNode));
		System.out.println(solution.isValidBST(treeNode1));
		System.out.println(solution.isValidBST(treeNode2));
	}

}
